#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "stack"

using namespace std;

/*HJJ QQ479287006
 示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：

输入：s = ""
输出：0
 
//思路 其实比较简单利用 栈的符号匹配把括号转成01  数组求 连续1 的数量
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。i*
 //todO 除了这种说法 dp 也得学
 * */
int longestValidParentheses(string s) {

    stack<int> st;
    vector<int> vec(s.size(), 0);
    for (int i = 0; i < s.size(); ++i) {
        //只能搞下标
        if (s[i] == '(') {
            st.push(i);
        } else {
            if (st.empty()) {
                continue;
            }
            int index = st.top();
            st.pop();
            vec[index] = 1;
            vec[i] = 1;
        }
    }


    int res = 0;
    int count = 0;
    //注意这个求数组也有说法啊 我草 如果不先continue 下面得求两次max
    for (int i = 0; i < vec.size(); ++i) {
        if (vec[i] != 1) {
            count = 0;
            continue;
        }

        count++;
        res = max(res, count);
    }


    return res;

}